import java.util.ArrayList;
import java.util.List;
import java.util.PriorityQueue;

public class 子序列累加和 {
    // 非负数组前k个最小的子序列累加和
    // 给定一个数组nums，含有n个数字，都是非负数
    // 给定一个正数k，返回所有子序列中累加和最小的前k个累加和
    // 子序列是包含空集的
    // 1 <= n <= 10^5
    // 1 <= nums[i] <= 10^6
    // 1 <= k <= 10^5
    // 注意这个数据量，用01背包的解法是不行的，时间复杂度太高了
    // 对数器验证


    public static int[] topKSum1(int[] nums, int k) {
        // 存储所有的和
        List<Integer> ans = new ArrayList<>();
        ans.add(0);
        ans.sort((a,b) -> a - b);
        dfs(nums,0,0,ans);
        int[] ret = new int[k];
        for (int i = 0; i < k; i++) {
            ret[i] = ans.get(i);
        }
        return ret;
    }

    private static void dfs(int[] nums, int pos, int sum, List<Integer> ans) {
        if (pos == nums.length) {
            ans.add(sum);
            return;
        } else {
            // 不选
            dfs(nums,pos + 1,sum,ans);
            // 选
            dfs(nums,pos + 1,sum + nums[pos],ans);
        }
    }
    public static int[] topKSum2(int[] nums, int k) {
        // 01 背包
        int sum = 0;
        for (int i = 0; i < nums.length; i++) {
            sum += nums[i];
        }
        boolean[] dp = new boolean[sum + 1];
        dp[0] = true;
        for (int i = 0; i < nums.length; i++) {
            for (int j = sum; j >= nums[i]; j--) {
                dp[j] = dp[j] || dp[j - nums[i]];
            }
        }
        int[] ans = new int[k];
        int cnt = 0;
        for (int i = 0; i <= sum; i++) {
            if (dp[i] && cnt < k){
                ans[cnt++] = i;
            }
        }
        return ans;
    }

    public static int[] topKSum3(int[] nums, int k) {
        // 用堆来进行维护最小值
        int[] ans = new int[k];
        int cnt = 0;
        PriorityQueue<Integer> heap = new PriorityQueue<>((a,b) -> a - b);
        heap.add(0);
        for (int i = 0; i < nums.length; i++) {
            int cur = heap.poll();
            if (cnt == k) {
                return ans;
            }
            // 一种是不要当前元素, 一种是要当前元素, 然后全部添加到堆里面
            heap.add(cur);
            heap.add(cur + nums[i]);
        }
        return ans;
    }
}
